/************************************************************************

								Heroes IV
					  Copyright 2000, The 3DO Company

	------------------------------------------------------------------
  							 transition_calculator.cpp

	$Header: /heroes4/transition_calculator.cpp $

	$NoKeywords: $

 ************************************************************************/

// kill the 255+ character identifier warning.  Templates tend to exceed that easily.
#include "precompiled.h"
#pragma warning( disable: 4786 )

#include "transition_calculator.h"

#include <algorithm>
#include <bitset>
#include <cassert>
#include <iterator>
#include <vector>

#include "abstract_adventure_map.h"
#include "abstract_tile.h"
#include "adventure_tile_size.h"
#include "direction.h"
#include "enum_operations.h"
#include "map_point.h"
#include "shroud_transition_map.h"
#include "transition_coordinates.h"

using namespace transition_calculator_details;

// -------------------------------------------------------------------------------
// Unnamed namespace
// -------------------------------------------------------------------------------

namespace
{

	// -------------------------------------------------------------------------------
	// t_terrain_mask_code_array class
	// -------------------------------------------------------------------------------

	class t_terrain_mask_code_array
	{
	public:
		// Member functions
		void clear();

		// Operators
		unsigned char &	operator[]( t_full_terrain_type index );
		unsigned char	operator[]( t_full_terrain_type index ) const;

	private:
		// Data members
		unsigned char	m_impl[ k_terrain_count ][ k_terrain_subtype_max ];
	};

	inline void t_terrain_mask_code_array::clear()
	{
		memset( m_impl, 0, sizeof( m_impl ) );
	}

	inline unsigned char & t_terrain_mask_code_array::operator[]( t_full_terrain_type index )
	{
		return m_impl[ index.get_type() ][ index.get_subtype() ];
	}

	inline unsigned char t_terrain_mask_code_array::operator[]( t_full_terrain_type index ) const
	{
		return m_impl[ index.get_type() ][ index.get_subtype() ];
	}

	// -------------------------------------------------------------------------------
	// t_road_mask_code_array class
	// -------------------------------------------------------------------------------

	class t_road_mask_code_array
	{
	public:
		// Member functions
		void clear();

		// Operators
		unsigned char &	operator[]( t_road_type index );
		unsigned char	operator[]( t_road_type index ) const;

	private:
		// Data members
		unsigned char	m_impl[ k_road_type_count ];
	};

	inline void t_road_mask_code_array::clear()
	{
		memset( m_impl, 0, sizeof( m_impl ) );
	}

	inline unsigned char & t_road_mask_code_array::operator[]( t_road_type index )
	{
		assert( index >= 0 && index < k_road_type_count );
		return m_impl[ index ];
	}

	inline unsigned char t_road_mask_code_array::operator[]( t_road_type index ) const
	{
		assert( index >= 0 && index < k_road_type_count );
		return m_impl[ index ];
	}

	// -------------------------------------------------------------------------------
	// t_shroud_mask_code_array class
	// -------------------------------------------------------------------------------

	class t_shroud_mask_code_array
	{
	public:
		// Member functions
		void clear();

		// Operators
		unsigned char &	operator[]( t_tile_visibility index );
		unsigned char	operator[]( t_tile_visibility index ) const;

	private:
		// Data members
		unsigned char	m_impl[ k_tile_visibility_count ];
	};

	inline void t_shroud_mask_code_array::clear()
	{
		memset( m_impl, 0, sizeof( m_impl ) );
	}

	inline unsigned char & t_shroud_mask_code_array::operator[]( t_tile_visibility index )
	{
		assert( index >= 0 && index < k_tile_visibility_count );
		return m_impl[ index ];
	}

	inline unsigned char t_shroud_mask_code_array::operator[]( t_tile_visibility index ) const
	{
		assert( index >= 0 && index < k_tile_visibility_count );
		return m_impl[ index ];
	}

	// -------------------------------------------------------------------------------
	// -------------------------------------------------------------------------------
	std::vector< unsigned char >	g_transition_ids[256];		// for transition masks xxxx, where 0 < x < 4
	unsigned char					g_corner_transitions[4];	// for transition masks like 0004
																// used only for 3+ terrain transitions

	void initialize_transition_ids()
	{
		static bool first_time = true;
		if ( !first_time )
			return;

		// initialize transition id arrays
		int id;
		int index;
		int code;

		id = 0;
		index = 0;
		while (k_transition_coordinates[index][0] >= 0)
		{
			code = translate_transition_code( k_transition_coordinates[index][2] );
			if (code >= 256)
				g_corner_transitions[ code - 256 ] = id++;
			else if (g_transition_ids[code].size() == 0)
				g_transition_ids[ code ].push_back( id++ );
			index++;
		}

		first_time = false;
	}

	// -------------------------------------------------------------------------------
	// terrain type priority order for edges
	// -------------------------------------------------------------------------------
	inline int get_edge_priority( t_full_terrain_type terrain_type )
	{
		static int const k_edge_priority[ k_terrain_count ] =
		{
			4,		// k_terrain_water,
			6,		// k_terrain_grass,
			7,		// k_terrain_rough,
			5,		// k_terrain_swamp,
			8,		// k_terrain_lava,
			9,		// k_terrain_snow,
			10,		// k_terrain_sand,
			11,		// k_terrain_dirt,
			12,		// k_terrain_subterranean,
			1,		// k_terrain_water_river,
			2,		// k_terrain_lava_river,
			3,		// k_terrain_ice_river,
			13,		// k_terrain_magic_all,
			14,		// k_terrain_magic_life,
			15,		// k_terrain_magic_order,
			16,		// k_terrain_magic_death,
			17,		// k_terrain_magic_chaos,
			18,		// k_terrain_magic_nature,
			19,		// k_terrain_might,
		};

		return k_edge_priority[ terrain_type.get_type() ] * ( k_terrain_subtype_max + 1 ) - terrain_type.get_subtype() - 1;
	}

	// -------------------------------------------------------------------------------
	// road type priority order for edges
	// -------------------------------------------------------------------------------
	inline int get_edge_priority( t_road_type road_type )
	{
		assert( road_type >= 0 && road_type < k_road_type_count );
		return k_road_type_count - road_type - 1;
	}

	// -------------------------------------------------------------------------------
	// visibility priority order for edges
	// -------------------------------------------------------------------------------
	inline int get_edge_priority( t_tile_visibility visibility )
	{
		assert( visibility >= 0 && visibility < k_tile_visibility_count );
		return visibility;
	}

	// -------------------------------------------------------------------------------
	// terrain type priority order for diagonals
	// -------------------------------------------------------------------------------
	inline int get_diagonal_priority( t_full_terrain_type terrain_type )
	{
		static int const k_diagonal_priority[ k_terrain_count ] =
		{
			1,		// k_terrain_water,
			3,		// k_terrain_grass,
			4,		// k_terrain_rough,
			2,		// k_terrain_swamp,
			5,		// k_terrain_lava,
			6,		// k_terrain_snow,
			7,		// k_terrain_sand,
			8,		// k_terrain_dirt,
			9,		// k_terrain_subterranean,
			17,		// k_terrain_water_river,
			18,		// k_terrain_lava_river,
			19,		// k_terrain_ice_river,
			10,		// k_terrain_magic_all,
			11,		// k_terrain_magic_life,
			12,		// k_terrain_magic_order,
			13,		// k_terrain_magic_death,
			14,		// k_terrain_magic_chaos,
			15,		// k_terrain_magic_nature,
			16,		// k_terrain_might,
		};

		return k_diagonal_priority[ terrain_type.get_type() ] * ( k_terrain_subtype_max + 1 ) - terrain_type.get_subtype() - 1;
	}

	// -------------------------------------------------------------------------------
	// road type priority order for diagonals
	// -------------------------------------------------------------------------------
	inline int get_diagonal_priority( t_road_type road_type )
	{
		assert( road_type >= 0 && road_type < k_road_type_count );
		return road_type;
	}

	// -------------------------------------------------------------------------------
	// visibility priority order for diagonals
	// -------------------------------------------------------------------------------
	inline int get_diagonal_priority( t_tile_visibility visibility )
	{
		assert( visibility >= 0 && visibility < k_tile_visibility_count );
		return k_tile_visibility_count - visibility - 1;
	}

	// -------------------------------------------------------------------------------
	// randomly select a water to land set
	// -------------------------------------------------------------------------------
	inline int select_water_to_land_set()
	{
		return k_transition_set_water_to_land + rand() % k_transition_set_size_water_to_land;
	}

	// -------------------------------------------------------------------------------
	// randomly select a land to water set
	// -------------------------------------------------------------------------------
	inline int select_land_to_water_set()
	{
		return k_transition_set_land_to_water + rand() % k_transition_set_size_land_to_water;
	}

	// -------------------------------------------------------------------------------
	// randomly select a land set
	// -------------------------------------------------------------------------------
	inline int select_land_set()
	{
		return k_transition_set_land + rand() % k_transition_set_size_land;
	}

	// -------------------------------------------------------------------------------
	// randomly select a road set
	// -------------------------------------------------------------------------------
	inline int select_road_set()
	{
		return k_transition_set_road + rand() % k_transition_set_size_road;
	}

	// -------------------------------------------------------------------------------
	// choose a transition set
	// -------------------------------------------------------------------------------
	int choose_set( t_full_terrain_type base_terrain, t_full_terrain_type adjacent_terrain )
	{
		typedef std::bitset< k_terrain_count > t_terrain_type_mask;
		static t_terrain_type_mask const k_watery_terrain_mask =
				t_terrain_type_mask( 1 ) << k_terrain_water
			|	t_terrain_type_mask( 1 ) << k_terrain_swamp
			|	t_terrain_type_mask( 1 ) << k_terrain_water_river
			|	t_terrain_type_mask( 1 ) << k_terrain_lava_river
			|	t_terrain_type_mask( 1 ) << k_terrain_ice_river;

		if ( base_terrain.get_type() == adjacent_terrain.get_type() )
		{
			if ( base_terrain.get_subtype() < adjacent_terrain.get_subtype() )
				return select_land_to_water_set();
			return select_water_to_land_set();
		}

		if ( k_watery_terrain_mask[ base_terrain ] )
			return select_land_to_water_set();

		if ( k_watery_terrain_mask[ adjacent_terrain ] )
			return select_water_to_land_set();

		return select_land_set();
	}

	// -------------------------------------------------------------------------------
	// choose a transition set for a pair of road types
	// -------------------------------------------------------------------------------
	int choose_set( t_road_type base_road_type, t_road_type adjacent_road_type )
	{
		if ( base_road_type != k_road_none && adjacent_road_type != k_road_none )
		{
			if ( base_road_type < adjacent_road_type )
				return select_land_to_water_set();
			return select_water_to_land_set();
		}

		return select_road_set();
	}

	// -------------------------------------------------------------------------------
	// choose a transition set for a pair of road types
	// -------------------------------------------------------------------------------
	int choose_set( t_tile_visibility base_visibility, t_tile_visibility adjacent_visibility )
	{
		if ( base_visibility < adjacent_visibility )
			return select_land_to_water_set();
		return select_water_to_land_set();
	}

	// -------------------------------------------------------------------------------
	// check if two transitions belong to the same basic set
	// -------------------------------------------------------------------------------
	inline int mask_group( int mask_set )
	{
		if (mask_set >= k_transition_set_water_to_land 
			&& mask_set < k_transition_set_water_to_land + k_transition_set_size_water_to_land)
			return k_transition_set_water_to_land;
		if (mask_set >= k_transition_set_land_to_water
			&& mask_set < k_transition_set_land_to_water + k_transition_set_size_land_to_water)
			return k_transition_set_land_to_water;
		if (mask_set >= k_transition_set_road
			&& mask_set < k_transition_set_road + k_transition_set_size_road)
			return k_transition_set_road;
		return k_transition_set_land;
	}

	inline bool same_group( int left, int right )
	{
		return mask_group( left ) == mask_group( right );
	}

	// -------------------------------------------------------------------------------
	// -------------------------------------------------------------------------------
	void clamp_to_map(
		int						map_size,
		t_screen_point const &	map_view_size,
		t_map_point_2d &		point )
	{
		int const k_half_tile_width = k_adventure_tile_width / 2;
		int const k_half_tile_height = k_adventure_tile_height / 2;

		int map_screen_height = map_size * k_adventure_tile_height;

		int point_sum = point.column + point.row;
		int point_diff = point.column - point.row;

		// Clamp to top edge
		int map_view_top = ( map_screen_height - map_view_size.y ) / 2;
		int top_edge_sum = map_view_top / k_half_tile_height - 1;
		if ( point_sum < top_edge_sum )
		{
			int offset = ( top_edge_sum - point_sum + 1 ) / 2;
			point.row += offset;
			point.column += offset;
		}
		else
		{
			// Clamp to bottom edge
			int map_view_bottom = map_view_top + map_view_size.y;
			int bottom_edge_sum = ( map_view_bottom + k_half_tile_height - 1 ) / k_half_tile_height - 1;

			if ( point_sum > bottom_edge_sum )
			{
				int offset = ( point_sum - bottom_edge_sum + 1 ) / 2;
				point.row -= offset;
				point.column -= offset;
			}
		}

		// Clamp to left edge
		int map_view_left = -map_view_size.x / 2;
		int left_edge_diff = ( map_view_left - ( k_half_tile_width - 1 ) ) / k_half_tile_width;
		if ( point_diff < left_edge_diff )
		{
			int offset = ( left_edge_diff - point_diff + 1 ) / 2;
			point.row -= offset;
			point.column += offset;
		}
		else
		{
			// Clamp to right edge
			int map_view_right = map_view_left + map_view_size.x;
			int right_edge_diff = ( map_view_right + k_half_tile_width - 1 ) / k_half_tile_width;
			if ( point_diff > right_edge_diff )
			{
				int offset = ( point_diff - right_edge_diff + 1 ) / 2;
				point.row += offset;
				point.column -= offset;
			}
		}

		// Handle corner cases
		if ( point.row < 0 )
			point.row = 0;
		else if ( point.row >= map_size )
			point.row = map_size - 1;

		if ( point.column < 0 )
			point.column = 0;
		else if ( point.column >= map_size )
			point.column = map_size - 1;
	}

	// -------------------------------------------------------------------------------
	// -------------------------------------------------------------------------------
	template < typename t_map >
	inline void clamp_to_map( t_map const & map, t_map_point_2d & point )
	{
		if ( !map.is_valid( point ) )
		{
			clamp_to_map( map.get_size(), map.get_view_size(), point );

			if ( !map.is_valid( point ) )
			{
				int row_start = map.get_row_start( point.row );
				if ( point.column < row_start )
					point.column = row_start;
				else
				{
					int row_end = map.get_row_end( point.row );
					if ( point.column >= row_end )
						point.column = row_end - 1;
				}
			}
		}
	}

	// -------------------------------------------------------------------------------
	// t_calculator_base_base_base class
	// -------------------------------------------------------------------------------

	class t_calculator_base_base_base
	{
	protected:
		// Data members
		int	m_diagonal_priority; // diagonal-transition priority of this tile
		int	m_edge_priority;     // edge-transition priority of this tile
		int	m_left_priority;     // edge-transition priority of left tile
		int	m_corner_priority;   // edge-transition priority of corner tile
		int	m_right_priority;    // edge-transition priority of right tile
		int	m_code_shift;        // bits to shift current transition code
	};

	// -------------------------------------------------------------------------------
	// t_calculator_base_base class template
	// -------------------------------------------------------------------------------

	template < typename t_tile_arg >
	class t_calculator_base_base : public t_calculator_base_base_base
	{
	protected:
		// Types
		typedef t_tile_arg	t_tile;

		// Data members
		t_tile	m_tile;
	};

	// -------------------------------------------------------------------------------
	// t_calculator_base class template
	// -------------------------------------------------------------------------------

	template < typename t_transition_traits >
	class t_calculator_base
		:	virtual protected t_calculator_base_base< typename t_transition_traits::t_tile >
	{
	protected:
		// Types
		typedef typename t_transition_traits::t_map			t_map;
		typedef typename t_transition_traits::t_type		t_type;
		typedef typename t_transition_traits::t_transition	t_transition;

		// Static member functions
		static void	merge_equivalent_transitions(
						std::vector< t_transition > const &	old_transition_vector,
						std::vector< t_transition > &		new_transition_vector );
		static bool	transition_vectors_differ(
						std::vector< t_transition > const & first_vector,
						std::vector< t_transition > const & second_vector );

		// Member functions
		void	calculate_transitions(
					t_map const &					map,
					t_level_map_point_2d const &	center_point,
					std::vector< t_transition > &	result );

	private:
		// Types
		typedef typename t_transition_traits::t_mask_code_array	t_mask_code_array;

		// Data members
		t_type						m_base_type;
		t_type						m_left_type;
		t_type						m_corner_type;
		t_type						m_right_type;
		t_mask_code_array			m_mask_code_array;
		std::vector< t_transition >	m_transition_stack;

		// Member functions
		void	add_transition( t_type type, int transition_type ); // add a transition code
		void	corner_is_same();                                   // corner terrain = tile
		void	left_is_same();                                     // left terrain = tile
		void	left_matches_right();                               // left terrain = right terrain
		void	right_is_same();                                    // right terrain = tile
		void	write_transitions( std::vector< t_transition > & result ); // translate to masks
	};

	// -------------------------------------------------------------------------------
	// t_calculator_base members
	// -------------------------------------------------------------------------------

	// -------------------------------------------------------------------------------
	// Determine if the transition vectors are equivalent to each other
	// -------------------------------------------------------------------------------
	template < typename t_transition_traits >
	bool t_calculator_base< t_transition_traits >::transition_vectors_differ(
		std::vector< t_transition > const & first_vector,
		std::vector< t_transition > const & second_vector )
	{
		if ( first_vector.size() != second_vector.size() )
			return true;

		std::vector< t_transition >::const_iterator first_iter = first_vector.begin();
		std::vector< t_transition >::const_iterator second_iter = second_vector.begin();
		for (	;
				first_iter != first_vector.end();
				++first_iter, ++second_iter )
		{
			if (	t_transition_traits::get_type( *first_iter ) != t_transition_traits::get_type( *second_iter )
				||	first_iter->get_id() != second_iter->get_id() )
				return true;
		}

		return false;
	}

	// -------------------------------------------------------------------------------
	// Adjust the ids of the new transitions to match any existing equivalent
	// transitions
	// -------------------------------------------------------------------------------
	template < typename t_transition_traits >
	void t_calculator_base< t_transition_traits >::merge_equivalent_transitions(
		std::vector< t_transition > const &	old_transition_vector,
		std::vector< t_transition > &		new_transition_vector )
	{
		std::vector< t_transition >::iterator new_transition_iter = new_transition_vector.begin();
		for (	;
				new_transition_iter != new_transition_vector.end();
				++new_transition_iter )
		{
			// Scan for an existing equivalent transition
			std::vector< t_transition >::const_iterator old_transition_iter = old_transition_vector.begin();
			for (	;
					old_transition_iter != old_transition_vector.end();
					++old_transition_iter )
			{
				if (	t_transition_traits::get_type( *new_transition_iter ) == t_transition_traits::get_type( *old_transition_iter )
					&&	new_transition_iter->get_id() == old_transition_iter->get_id()
					&&	same_group( new_transition_iter->get_mask_set(), old_transition_iter->get_mask_set() ) )
				{
					// Found an equivalent transition so use the same mask set
					new_transition_iter->set_mask_set( old_transition_iter->get_mask_set() );
					break;
				}
			}
		}
	}

	// -------------------------------------------------------------------------------
	// -------------------------------------------------------------------------------
	template < typename t_transition_traits >
	void t_calculator_base< t_transition_traits >::calculate_transitions(
		t_map const &					map,
		t_level_map_point_2d const &	center_point,
		std::vector< t_transition > &	result )
	{
		t_direction base_angle;

		m_base_type = t_transition_traits::get_type( m_tile );

		m_diagonal_priority = get_diagonal_priority( m_base_type );
		m_edge_priority     = get_edge_priority( m_base_type );
		m_code_shift        = 0;
		m_transition_stack.clear();

		m_mask_code_array.clear();

		for (	base_angle = t_direction( 1 );
				base_angle < k_direction_count;
				enum_incr( base_angle, 2 ), m_code_shift += 2 )
		{
			t_tile left_tile = t_transition_traits::get_tile( map, center_point, counter_clockwise( base_angle ) );
			t_tile corner_tile = t_transition_traits::get_tile( map, center_point, base_angle );
			t_tile right_tile = t_transition_traits::get_tile( map, center_point, clockwise( base_angle ) );

			m_left_type = t_transition_traits::get_type( left_tile );
			m_left_priority = get_edge_priority( m_left_type );

			m_corner_type = t_transition_traits::get_type( corner_tile );
			m_corner_priority = get_edge_priority( m_corner_type );

			m_right_type = t_transition_traits::get_type( right_tile );
			m_right_priority = get_edge_priority( m_right_type );

			// handle cases where left tile is the same as this tile.
			if ( m_left_type == m_base_type )
			{
				left_is_same();
				continue;
			}

			// handle cases where right tile is the same as this tile.
			if ( m_right_type == m_base_type )
			{
				right_is_same();
				continue;
			}

			// handle cases where corner tile is the same as this tile
			if ( m_corner_type == m_base_type )
			{
				corner_is_same();
				continue;	
			}

			// handle case where left & right are the same.
			if ( m_left_type == m_right_type )
			{
				left_matches_right();
				continue;
			}

			// add left & right transitions, as appropriate.
			if ( m_left_priority > m_edge_priority )
				add_transition( m_left_type, k_transition_left );

			if ( m_right_priority > m_edge_priority )
				add_transition( m_right_type, k_transition_right );

			// add a corner transition, if appropriate.
			if (	m_corner_priority > m_edge_priority
				&&	m_corner_priority > m_left_priority 
				&&	m_corner_priority > m_right_priority )
				add_transition( m_corner_type, k_transition_corner );
		}

		write_transitions( result );
	}

	// -------------------------------------------------------------------------------
	// add a partial mask
	// ------------------------------------------------------------------------------
	template < typename t_transition_traits >
	void t_calculator_base< t_transition_traits >::add_transition( t_type type, int transition_type )
	{
		if ( transition_type == k_transition_corner )
		{
			t_transition transition;

			t_transition_traits::set_type( transition, type );
			transition.set_id( g_corner_transitions[ m_code_shift / 2 ] );
			transition.set_mask_set( choose_set( m_base_type, type ) );

			m_transition_stack.push_back( transition );
		}
		else
			m_mask_code_array[ type ] |= transition_type << m_code_shift;
	}

	// -------------------------------------------------------------------------------
	// handle cases where left tile is the same as this tile.
	// -------------------------------------------------------------------------------
	template < typename t_transition_traits >
	void t_calculator_base< t_transition_traits >::left_is_same()
	{
		// if both left & right are the same as this, no transition.
		if ( m_right_type == m_base_type )
			return;

		// if both left & corner are the same as this, no transition.
		if ( m_corner_type == m_base_type )
			return;

		// add a right transition, if appropriate.
		if ( m_right_priority > m_edge_priority )
			add_transition( m_right_type, k_transition_right );

		// check case where we need a corner because the corner is different from the
		// right AND this tile.
		if (	m_corner_type != m_right_type
			&&	m_corner_priority > m_right_priority
			&&	m_corner_priority > m_edge_priority )
			add_transition( m_corner_type, k_transition_corner );
	}

	// -------------------------------------------------------------------------------
	// handle cases where right tile is the same as this tile.
	// -------------------------------------------------------------------------------
	template < typename t_transition_traits >
	void t_calculator_base< t_transition_traits >::right_is_same()
	{
		// if both right & diagonal are the same as this, no transition.
		if ( m_corner_type == m_base_type )
			return;

		// add a left transition, if appropriate.
		if ( m_left_priority > m_edge_priority )
			add_transition( m_left_type, k_transition_left );

		// check case where we need a corner because the corner is different from the
		// left AND this tile.
		if (	m_corner_type != m_left_type
			&&	m_corner_priority > m_left_priority 
			&&	m_corner_priority > m_edge_priority )
			add_transition( m_corner_type, k_transition_corner );
	}

	// -------------------------------------------------------------------------------
	// handle cases where corner is the same, but right and left are different
	// -------------------------------------------------------------------------------
	template < typename t_transition_traits >
	void t_calculator_base< t_transition_traits >::corner_is_same()
	{
		// if we have a higher diagonal priority, no transition (we're making
		// a diagonal link to the corner tile)
		if (	get_diagonal_priority( m_right_type ) < m_diagonal_priority
			&&	get_diagonal_priority( m_left_type ) < m_diagonal_priority )
			return;

		// if both left & right are the same, make a diagonal transition
		if ( m_left_type == m_right_type )
		{
			add_transition( m_left_type, k_transition_diagonal );
			return;
		}

		// add left & right transitions, as appropriate.
		if ( m_left_priority > m_edge_priority )
			add_transition( m_left_type, k_transition_left );

		if ( m_right_priority > m_edge_priority )
			add_transition( m_right_type, k_transition_right );
	}

	// -------------------------------------------------------------------------------
	// handle case where left & right are the same, but neither matches this tile
	// -------------------------------------------------------------------------------
	template < typename t_transition_traits >
	void t_calculator_base< t_transition_traits >::left_matches_right()
	{
		// if all 3 are the same, make a diagonal transition and stop.
		if ( m_left_type == m_corner_type )
		{
			add_transition( m_left_type, k_transition_diagonal );
			return;
		}

		// if left & right diagonal priority is higher than both this and the corner,
		// make a diagonal transition and stop.
		if (	get_diagonal_priority( m_left_type ) > m_diagonal_priority 
			&&	get_diagonal_priority( m_left_type ) > get_diagonal_priority( m_corner_type ) )
		{
			add_transition( m_left_type, k_transition_diagonal );
			return;
		}

		// corner is different from both left and right, and this.
		// make a diagonal transition if this tile is a lower priority than the left 
		// and right tiles.
		if ( m_left_priority > m_edge_priority )
			add_transition( m_left_type, k_transition_diagonal );

		if ( m_corner_priority > m_edge_priority && m_corner_priority > m_left_priority )
			add_transition( m_corner_type, k_transition_corner );
	}

	// -------------------------------------------------------------------------------
	// write actual transitions to tile
	// -------------------------------------------------------------------------------
	template < typename t_transition_traits >
	void t_calculator_base< t_transition_traits >::write_transitions( std::vector< t_transition > & result )
	{
		std::vector< t_transition > new_transition_vector;

		int evaluation_count = t_transition_traits::get_evaluation_type_count();
		int evaluation_num;
		for ( evaluation_num = 0; evaluation_num < evaluation_count; ++evaluation_num )
		{
			t_type adjacent_type = t_transition_traits::get_evaluation_type( evaluation_num );

			if ( m_mask_code_array[ adjacent_type ] == 0 )
				continue;

			int code = m_mask_code_array[ adjacent_type ];
			std::vector< unsigned char > const & transition_list = g_transition_ids[ code ];

			new_transition_vector.push_back( t_transition() );
			t_transition & new_transition = new_transition_vector.back();;

			t_transition_traits::set_type( new_transition, adjacent_type );
			new_transition.set_id( transition_list[ 0 ] );
			new_transition.set_mask_set( choose_set( m_base_type, adjacent_type ) );
		}

		if ( !m_transition_stack.empty() )
		{
			new_transition_vector.reserve( new_transition_vector.size() + m_transition_stack.size() );
			std::copy(
				m_transition_stack.begin(),
				m_transition_stack.end(),
				std::back_inserter( new_transition_vector ) );
		}

		result.swap( new_transition_vector );
	}

	// -------------------------------------------------------------------------------
	// Helper function for t_terrain_transition_traits below
	// -------------------------------------------------------------------------------
	std::vector< t_full_terrain_type > const & get_terrain_evaluation_type_vector()
	{
		static t_terrain_type const k_evaluation_order[ k_terrain_count ] =
		{
			k_terrain_water_river,
			k_terrain_lava_river,
			k_terrain_ice_river,
			k_terrain_water,
			k_terrain_grass,
			k_terrain_rough,
			k_terrain_swamp,
			k_terrain_lava,
			k_terrain_snow,
			k_terrain_sand,
			k_terrain_dirt,
			k_terrain_subterranean,
			k_terrain_magic_all,
			k_terrain_magic_life,
			k_terrain_magic_order,
			k_terrain_magic_death,
			k_terrain_magic_chaos,
			k_terrain_magic_nature,
			k_terrain_might,
		};

		static std::vector< t_full_terrain_type > type_vector;
		static bool first_time = true;

		if ( first_time )
		{
			// Build the vector of terrain type/subtype combos to evaluate
			int i;
			for ( i = 0; i < k_terrain_count; ++i )
			{
				t_terrain_type terrain_type = k_evaluation_order[ i ];
				int subtype_count = get_terrain_subtype_count( terrain_type );
				int terrain_subtype;
				for ( terrain_subtype = 0; terrain_subtype < subtype_count; ++terrain_subtype )
					type_vector.push_back( t_full_terrain_type( terrain_type, terrain_subtype ) );
			}

			// Shrink the vector to fit
			std::vector< t_full_terrain_type >( type_vector ).swap( type_vector );

			first_time = false;
		}

		return type_vector;
	}

	// -------------------------------------------------------------------------------
	// t_terrain_transition_traits_base struct
	// -------------------------------------------------------------------------------

	struct t_terrain_transition_traits_base
	{
	public:
		// Types
		typedef t_abstract_terrain_map	t_map;
		typedef t_abstract_tile const *	t_tile;

		// Static member functions
		static t_tile	get_tile(
							t_map const &					map,
							t_level_map_point_2d const &	point,
							t_direction						direction );
	};

	t_abstract_tile const * t_terrain_transition_traits_base::get_tile(
		t_map const &					map,
		t_level_map_point_2d const &	point,
		t_direction						direction )
	{
		assert( direction >= 0 && direction < k_direction_count );
		t_level_map_point_2d adjacent_point = point + get_direction_offset( direction );
		clamp_to_map( map, adjacent_point );
		return &map.get_tile( adjacent_point );
	}

	// -------------------------------------------------------------------------------
	// t_terrain_transition_traits struct
	// -------------------------------------------------------------------------------

	struct t_terrain_transition_traits : public t_terrain_transition_traits_base
	{
	public:
		// Types
		typedef t_full_terrain_type			t_type;
		typedef t_terrain_transition		t_transition;
		typedef t_terrain_mask_code_array	t_mask_code_array;

		// Static member functions
		static int		get_evaluation_type_count();
		static t_type	get_evaluation_type( int evaluation_num );
		static t_type	get_type( t_tile tile );
		static t_type	get_type( t_transition const & transition );
		static void		set_type( t_transition & transition, t_type new_type );
	};

	inline int t_terrain_transition_traits::get_evaluation_type_count()
	{
		static std::vector< t_full_terrain_type > const & k_type_vector = get_terrain_evaluation_type_vector();
		return k_type_vector.size();
	}

	inline t_full_terrain_type t_terrain_transition_traits::get_evaluation_type( int evaluation_num )
	{
		static std::vector< t_full_terrain_type > const & k_type_vector = get_terrain_evaluation_type_vector();
		assert( evaluation_num >= 0 && evaluation_num < k_type_vector.size() );
		return k_type_vector[ evaluation_num ];
	}

	inline t_full_terrain_type t_terrain_transition_traits::get_type( t_tile tile )
	{
		assert( tile != 0 );
		return t_type( tile->get_terrain(), tile->get_terrain_subtype() );
	}

	inline t_full_terrain_type t_terrain_transition_traits::get_type( t_transition const & transition )
	{
		return t_type( transition.get_terrain(), transition.get_terrain_subtype() );
	}

	inline void t_terrain_transition_traits::set_type( t_transition & transition, t_type new_type )
	{
		transition.set_terrain( new_type.get_type() );
		transition.set_terrain_subtype( new_type.get_subtype() );
	}

	// -------------------------------------------------------------------------------
	// t_road_transition_traits struct
	// -------------------------------------------------------------------------------

	struct t_road_transition_traits : public t_terrain_transition_traits_base
	{
	public:
		// Types
		typedef t_road_type				t_type;
		typedef t_road_transition		t_transition;
		typedef t_road_mask_code_array	t_mask_code_array;

		// Static member functions
		static int		get_evaluation_type_count();
		static t_type	get_evaluation_type( int evaluation_num );
		static t_type	get_type( t_tile tile );
		static t_type	get_type( t_transition const & transition );
		static void		set_type( t_transition & transition, t_type new_type );
	};

	inline int t_road_transition_traits::get_evaluation_type_count()
	{
		return k_road_type_count;
	}

	inline t_road_type t_road_transition_traits::get_evaluation_type( int evaluation_num )
	{
		assert( evaluation_num >= 0 && evaluation_num < k_road_type_count );
		return t_road_type( k_road_type_count - evaluation_num - 1 );
	}

	inline t_road_type t_road_transition_traits::get_type( t_tile tile )
	{
		assert( tile != 0 );
		return tile->get_road_type();
	}

	inline t_road_type t_road_transition_traits::get_type( t_transition const & transition )
	{
		return transition.get_road_type();
	}

	inline void t_road_transition_traits::set_type( t_transition & transition, t_type new_type )
	{
		transition.set_road_type( new_type );
	}

	// -------------------------------------------------------------------------------
	// -------------------------------------------------------------------------------
	typedef t_calculator_base< t_terrain_transition_traits >	t_terrain_transition_calculator;
	typedef t_calculator_base< t_road_transition_traits >		t_road_transition_calculator;

	// -------------------------------------------------------------------------------
	// t_shroud_map struct
	// -------------------------------------------------------------------------------

	struct t_shroud_map
	{
		// Data members
		t_abstract_adventure_map const *	adventure_map_ptr;
		int									team_num;
	};

	// -------------------------------------------------------------------------------
	// t_shroud_tile struct
	// -------------------------------------------------------------------------------

	struct t_shroud_tile
	{
		// Data members
		t_abstract_adventure_tile const *	tile_ptr;
		int									team_num;

		// Constructor
		t_shroud_tile() {}
		t_shroud_tile(
			t_abstract_adventure_tile const *	tile_ptr_arg,
			int									team_num_arg );
	};

	inline t_shroud_tile::t_shroud_tile(
		t_abstract_adventure_tile const *	tile_ptr_arg,
		int									team_num_arg )
		:	tile_ptr( tile_ptr_arg ),
			team_num( team_num_arg )
	{
	}

	// -------------------------------------------------------------------------------
	// t_shroud_transition_traits struct
	// -------------------------------------------------------------------------------

	struct t_shroud_transition_traits
	{
	public:
		// Types
		typedef t_shroud_map				t_map;
		typedef t_shroud_tile				t_tile;
		typedef t_tile_visibility			t_type;
		typedef t_shroud_transition			t_transition;
		typedef t_shroud_mask_code_array	t_mask_code_array;

		// Static member functions
		static int		get_evaluation_type_count();
		static t_type	get_evaluation_type( int evaluation_num );
		static t_tile	get_tile(
							t_map const &					map,
							t_level_map_point_2d const &	point,
							t_direction						direction );
		static t_type	get_type( t_tile tile );
		static t_type	get_type( t_transition const & transition );
		static void		set_type( t_transition & transition, t_type new_type );
	};

	inline int t_shroud_transition_traits::get_evaluation_type_count()
	{
		return k_tile_visibility_count;
	}

	inline t_tile_visibility t_shroud_transition_traits::get_evaluation_type(
		int	evaluation_num )
	{
		assert( evaluation_num >= 0 && evaluation_num < k_tile_visibility_count );
		return t_tile_visibility( evaluation_num );
	}

	t_shroud_tile t_shroud_transition_traits::get_tile(
		t_map const &					map,
		t_level_map_point_2d const &	point,
		t_direction						direction )
	{
		assert( map.adventure_map_ptr != 0 );
		assert( direction >= 0 && direction < k_direction_count );

		t_level_map_point_2d adjacent_point = point + get_direction_offset( direction );
		clamp_to_map( *map.adventure_map_ptr, adjacent_point );
		return t_tile( &map.adventure_map_ptr->get_tile( adjacent_point ), map.team_num );
	}

	inline t_tile_visibility t_shroud_transition_traits::get_type( t_tile tile )
	{
		assert( tile.tile_ptr != 0 );
		return tile.tile_ptr->get_visibility( tile.team_num );
	}

	inline t_tile_visibility t_shroud_transition_traits::get_type( t_transition const & transition )
	{
		return transition.get_visibility();
	}

	inline void t_shroud_transition_traits::set_type( t_transition & transition, t_type new_type )
	{
		transition.set_visibility( new_type );
	}

	// -------------------------------------------------------------------------------
	// -------------------------------------------------------------------------------
	typedef t_calculator_base< t_shroud_transition_traits > t_shroud_calculator_base;

} // Unnamed namespace

// -------------------------------------------------------------------------------
// t_transition_calculator::t_impl class
// -------------------------------------------------------------------------------

class t_transition_calculator::t_impl
	:	private t_terrain_transition_calculator,
		private t_road_transition_calculator
{
public:
	t_impl();

	// Returns true if the transitions have changed
	bool set_transitions( t_abstract_terrain_map & map, t_level_map_point_2d const & point );
};


// -------------------------------------------------------------------------------
// class to calculate correct transition mask, given a cell in an abstract_map
// -------------------------------------------------------------------------------
t_transition_calculator::t_impl::t_impl()
{
	initialize_transition_ids();
}

// -------------------------------------------------------------------------------
// class to calculate correct transition mask, given a cell in an abstract_map
// -------------------------------------------------------------------------------
bool t_transition_calculator::t_impl::set_transitions(
	t_abstract_terrain_map &		map, 
	t_level_map_point_2d const &	center_point )
{
	if ( !map.is_valid( center_point ) )
		return false;

	m_tile = &map.get_const_tile( center_point );

	std::vector< t_terrain_transition > new_terrain_transitions;
	std::vector< t_road_transition > new_road_transitions;

	t_terrain_transition_calculator::calculate_transitions( map, center_point, new_terrain_transitions );
	t_road_transition_calculator::calculate_transitions( map, center_point, new_road_transitions );

	std::vector< t_terrain_transition > const & old_terrain_transitions = m_tile->get_terrain_transition_vector();
	std::vector< t_road_transition > const & old_road_transitions = m_tile->get_road_transition_vector();

	bool terrain_transitions_changed =
		t_terrain_transition_calculator::transition_vectors_differ( old_terrain_transitions, new_terrain_transitions );

	bool road_transitions_changed =
		t_road_transition_calculator::transition_vectors_differ( old_road_transitions, new_road_transitions );

	if ( !terrain_transitions_changed && !road_transitions_changed )
		return false;

	if ( terrain_transitions_changed )
		t_terrain_transition_calculator::merge_equivalent_transitions( old_terrain_transitions, new_terrain_transitions );
	else
		std::copy( old_terrain_transitions.begin(), old_terrain_transitions.end(), new_terrain_transitions.begin() );

	if ( road_transitions_changed )
		t_road_transition_calculator::merge_equivalent_transitions( old_road_transitions, new_road_transitions );
	else
		std::copy( old_road_transitions.begin(), old_road_transitions.end(), new_road_transitions.begin() );

	t_abstract_tile & tile = map.get_tile( center_point );
	tile.swap_transition_vectors( new_terrain_transitions, new_road_transitions );

	return true;
}

// -------------------------------------------------------------------------------
// t_transition_calculator members
// -------------------------------------------------------------------------------

// -------------------------------------------------------------------------------
// -------------------------------------------------------------------------------
t_transition_calculator::t_transition_calculator()
	:	m_impl_ptr( new t_impl )
{
}

// -------------------------------------------------------------------------------
// -------------------------------------------------------------------------------
t_transition_calculator::~t_transition_calculator()
{
}

// -------------------------------------------------------------------------------
// -------------------------------------------------------------------------------
bool t_transition_calculator::do_set_transitions(
	t_abstract_terrain_map &		map,
	t_level_map_point_2d const &	point )
{
	return m_impl_ptr->set_transitions( map, point );
}

// -------------------------------------------------------------------------------
// t_shroud_transition_calculator::t_impl class
// -------------------------------------------------------------------------------

class t_shroud_transition_calculator::t_impl
	:	private t_shroud_calculator_base
{
public:
	// Constructor
	t_impl();

	// Member functions
	bool	set_transitions(
				t_abstract_adventure_map &		map,
				int								team_num,
				t_level_map_point_2d const &	point );
};

// -------------------------------------------------------------------------------
// t_shroud_transition_calculator::t_impl members
// -------------------------------------------------------------------------------

// -------------------------------------------------------------------------------
// -------------------------------------------------------------------------------
t_shroud_transition_calculator::t_impl::t_impl()
{
	initialize_transition_ids();
}

// -------------------------------------------------------------------------------
// -------------------------------------------------------------------------------
bool t_shroud_transition_calculator::t_impl::set_transitions(
	t_abstract_adventure_map &		map,
	int								team_num,
	t_level_map_point_2d const &	point )
{
	if ( !map.is_valid( point ) )
		return false;

	t_shroud_transition_map const * transition_map_ptr =
		map.get_const_shroud_transition_map_ptr( team_num );
	if ( transition_map_ptr == 0 )
		return false;

	m_tile = t_shroud_tile( &map.get_const_tile( point ), team_num );

	t_shroud_map shroud_map;
	shroud_map.adventure_map_ptr = &map;
	shroud_map.team_num = team_num;

	std::vector< t_shroud_transition > new_transitions;
	calculate_transitions( shroud_map, point, new_transitions );

	std::vector< t_shroud_transition > const & old_transitions = transition_map_ptr->get_transitions( point );

	if ( !transition_vectors_differ( old_transitions, new_transitions ) )
		return false;

	merge_equivalent_transitions( old_transitions, new_transitions );
	map.get_shroud_transition_map_ptr( team_num )->take_transitions( point, new_transitions );

	return true;
}

// -------------------------------------------------------------------------------
// t_shroud_transition_calculator members
// -------------------------------------------------------------------------------

// -------------------------------------------------------------------------------
// -------------------------------------------------------------------------------
t_shroud_transition_calculator::t_shroud_transition_calculator()
	:	m_impl_ptr( new t_impl )
{
}

// -------------------------------------------------------------------------------
// -------------------------------------------------------------------------------
t_shroud_transition_calculator::~t_shroud_transition_calculator()
{
}

// -------------------------------------------------------------------------------
// -------------------------------------------------------------------------------
bool t_shroud_transition_calculator::set_transitions(
	t_abstract_adventure_map &		map,
	int								team_num,
	t_level_map_point_2d const &	point )
{
	return m_impl_ptr->set_transitions( map, team_num, point );
}
